The advent of Internet commerce has increased the prevalence of e-tickets. E-tickets permit consumers to reserve goods and services in advance of the consumption of those goods or services. During an Internet session, for example, a user may visit a web site to make travel arrangements including flight and car reservations. The user is provided with a unique confirmation key or e-ticket for the reserved goods or services. Subsequently, the user must present the e-ticket in order to utilize or obtain the reserved services or goods. A validation protocol is used to determine whether the submitted e-ticket is valid based on a number of requirements. Once the e-ticket is determined to be valid, the e-ticket can be accepted so that the goods or services may be provided to the user.
Typically, the e-ticket is only valid for a single use. One validation protocol simply assumes that the user will not attempt to use the e-ticket more than once. Such protocols are susceptible to abuse by malicious users. Unlike paper tickets, e-tickets need not be relinquished when submitted. Copies are readily and inexpensively made. Thus a user may intentionally or unintentionally resubmit the same e-ticket or even distribute the e-ticket for submission by others.
Another validation protocol relies on a centralized server to ensure the issuance of unique e-tickets and to ensure that a valid e-ticket is accepted only once. One disadvantage of this approach is that the entire protocol has a single point of failure. If the centralized server crashes, valid e-tickets cannot be accepted. Thus this approach is not sufficiently robust to withstand a failure in the centralized server.
A failure detection mechanism can be introduced to support failovers to backup servers when the centralized server crashes. One disadvantage of this approach is the reliance upon perfect failure detection. Mistakes in failure detection result in unexpected behavior.
The failure detection mechanisms may determine that a server has crashed based on a period of non-responsiveness. The length of time that the failure detection mechanism must wait when determining non-responsiveness necessarily trades off false positive diagnosis for false negative diagnosis at least for a period of time. If the server has crashed, the failure detection mechanism may not indicate such until after the expiration of a pre-determined time period during which a false negative condition is effectively occurring. Similarly, if the server has not crashed but is very busy, the failure detection mechanism may indicate that the server has crashed when in fact the server is simply too busy during the pre-determined time period to respond. Either of these conditions may lead to unexpected or undesired behavior.
For example, multiple acceptance could occur if a backup server takes over when the centralized server was non-responsive due to workload as opposed to an actual crash (i.e., false positive). Alternatively, no acceptance might occur if the backup server fails to take over when the centralized server has crashed (false negative).